The authors introduce numerical sparsity'' as a new parameter to measure the efficiency of algorithms for solving these problems. For a vector x, its numerical sparsity is defined to be x _1 2 / x _2 2. This quantity is a softer'' version of sparsity and is never larger than the l_0 sparsity of x. The main new insight of this paper is that, it is possible to achieve better running time if we measure the efficiency of algorithms using this new parameter. To accomplish this goal, instead of devising completely new convex optimization methods, the authors develop new stochastic gradient oracle for these problems by importance sampling the matrix A (Section 3), whose variance bound depends on the numerical sparsity of rows of A, and then directly apply existing stochastic first order methods to solve l_2 regression and top eigenvector computation (Section 4). The main new technical result in this paper is an unbiased stochastic oracle to estimate A T Ax for a matrix A and a vector x, which can serve as a stochastic gradient oracle when solving l_2 regression and top eigenvector computation. The variance of the oracle depends on the numerical sparsity of rows of A. I found this idea interesting and natural: consider a sparse vector a, if we slightly perturb a then its l_0 sparsity would be large. However, it is still possible to estimate such vector a accurately by (i) finding out heavy coordinates of a and (ii) importance sampling coordinates according to their magnitudes. The authors develop new stochastic oracle to estimate A T Ax by formalizing these intuitions in Section 3. The main difficulty here is to relate the variance to the function error, and the authors achieve this goal by exploiting the numerical sparsity of rows of A. I found this sampling procedure interesting and may have applications in other machine learning / numerical linear algebra tasks. Overall, this is a good paper and I would recommend acceptance.